class Node{
    constructor(element){
        this.element = element;
        this.left = null;
        this.right = null;
    }   
}

class Tree{
    constructor() {
        this.root = null;
        this.postArr = []; //后序遍历的值
        this.preArr = [];  //前序遍历的值
    }

    //插入  左侧子节点比父节点小，右侧子节点比父节点大
    insert(element){
        //1.创建节点
        let node = new Node(element);
        if(this.root === null){
            //树为空
            this.root = node;
        }else{
            this.insertNode(node,this.root);
        }
    }

    insertNode(newNode,rootNode){
        if(newNode.element < rootNode.element){
            //左边
            if(rootNode.left === null){
                rootNode.left = newNode;
            }else{
                this.insertNode(newNode,rootNode.left);
            }
        }else{
            //右边
            if(rootNode.right === null){
                rootNode.right = newNode;
            }else{
                this.insertNode(newNode,rootNode.right);
            }
        }
    }

    //前序遍历
    preOrderTraverse(){
        return this.preOrderTraverseNode(this.root);
    }

    preOrderTraverseNode(node){
        if(node != null){
            this.preArr.push(node.element);//打印节点的值
            this.preOrderTraverseNode(node.left);
            this.preOrderTraverseNode(node.right);
        }
    }

    //后序遍历
    postOrderTraverse(){
        return this.postOrderTraverseNode(this.root);
    }

    postOrderTraverseNode(node){
        if(node != null){
            this.postOrderTraverseNode(node.left);
            this.postOrderTraverseNode(node.right);
            this.postArr.push(node.element);//打印节点的值
        }
    }

    //查找最小子节点
    min(){
        return this.minNode(this.root);
    }

    minNode(node){
        if(node.left === null){
            return node
        }
        return this.minNode(node.left);
    }

    //搜索
    search(element){  //true false
        return this.searchNode(element,this.root);
    }

    searchNode(element,rootNode){
        if(rootNode === null){
            return false;
        }
        if(element < rootNode.element){
            //左侧查找
            return this.searchNode(element,rootNode.left);
        }else if(element > rootNode.element){
            //右侧查找
            return this.searchNode(element,rootNode.right);
        }else{
            //相等
            return true
        }
    }
}

let tree = new Tree();

tree.insert(11);

tree.insert(7)

tree.insert(15);

tree.insert(5);

tree.insert(13);

tree.insert(20);

tree.insert(12);

tree.insert(14);

tree.insert(18);

tree.insert(25);

//前序遍历
tree.preOrderTraverse();

console.log(tree.preArr);

// //后序遍历
tree.postOrderTraverse();

console.log(tree.postArr);

// console.log(tree.min())

console.log(tree.search(6))

// tree.remove(15);

// console.log(tree);

//冒泡排序的方法

function bubbleSort(arr=[]){
    let {length} = arr; //10
    for(let i = 0;i<length;i++){
        for(let j = 0;j<length-1-i;j++){  //0 1 2 3 4 5 6 7 8
            if(arr[j] > arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]];
            }
        }
    }
    return arr
}

console.log(bubbleSort(tree.preArr))

//选择排序的方法

function selectSort(arr=[]){

    let {length} = arr;

    let min;
    for(let i = 0;i<length;i++){
        min = i;
        for(let j = i+1;j<length;j++){
            //比较大小
            if(arr[min] > arr[j]){
                min = j;
            }
        }
        //初始min的值和最后最小值下标不一致
        if(min != i){
            [arr[min],arr[i]] = [arr[i],arr[min]]
        }
    }

    return arr
}

console.log(selectSort(tree.postArr))